1. Field
Embodiments of the invention relate to the field of networking; and more specifically, to detecting large flows in networks.
2. Background Information
In many networks it is often the case that a small proportion of large flows use a disproportionately large proportion of the overall bandwidth and other network resources. These large flows are sometimes referred to as elephant flows or heavy hitter flows. Similarly, a large proportion of small flows often use only a small proportion of the overall bandwidth and other network resources. These small flows are sometimes referred to as mice flows. By way of example, in some networks, the largest 10% of the flows may use more than 80% of the bandwidth and other network resources.
It is often desirable to be able to identify or detect such large flows so that they may be handled differently than small flows, or for various other purposes associated with network monitoring, network management, or other purposes. As one example, the identified large flows may be used for billing and/or accounting (e.g., the large flows may be charged differently than the small flows). As another example, the identified large flows may be used for bandwidth management and/or traffic engineering (e.g., to reroute traffic, upgrading links, etc.). As a further example, the identified large flows may be used to manage congestion and/or quality of service (e.g., by dropping packets of large flows, de-prioritizing large flows, applying a rate-limiting policy, or otherwise penalizing large flows). As yet another example, the identified large flows may be used to help detect or analyze a denial of service (DoS) attack. A still further example may involve using the identified large flows for service flow offload (e.g., in which deep packet inspection, security, or other heavy processing is bypassed for packets of large flows). These are just a few illustrative examples.
Various different approaches are known in the arts to attempt to detect or identify such heavy hitter flows, elephant flows, or other large flows. Often, in these approaches counters are used to count packets or sampled packets of the flows.
In one approach, a different counter is provided for each different flow. The counter is incremented each time a packet is received for the corresponding flow. Incrementing the counter basically counts the number of packets received for the corresponding flow. However, often the number of different flows may be relatively large. As a result, one possible drawback with such an approach is that including a counter for each different flow may tend to be prohibitive in terms of the amount of memory and memory access bandwidth resources needed to implement the relatively large number of counters.
Various other approaches attempt to use more elaborate mechanisms to detect large flows in order to reduce the amount of memory and other resources. One approach is described in the paper “NEW DIRECTIONS IN TRAFFIC MEASUREMENT AND ACCOUNTING,” by Cristian Estan et al., published in Proceedings of ACM SIGCOMM, pp. 323-336, August 2002. This reference describes an approach for identifying large flows that involves sample and hold and multistage filters. The sample and hold samples packets with a probability. If a packet is sampled and the flow it belongs to is not currently being tracked (e.g., does not yet have a counter), then a new entry is created in the flow monitoring memory to track that flow. After an entry is created for the flow, the counters are updated for every subsequent packet of the flow, not just for sampled packets of that flow. The parallel multistage filters operate in parallel. A packet flow identifier is hashed with different hash functions to identify a counter in each of the different filter stages arranged in parallel, and the different counters in each of the different parallel filter stages are updated to account for the packet. There is also a proposal of a serial multistage filter.
However, one possible drawback with the parallel multistage filters discusses in this reference is that over time there tends to be a decrease in the ability of the parallel multistage filters to detect large flows. All of the counters may reach their thresholds or maximum values and no longer increment. The reference describes that the flow memory and counters may be erased or reset at intervals. However, this erasing or resetting of the counters tends to introduce a discontinuity in large flow detection and adds additional latency to large flow detection. A way of using the parallel multistage filters for continuous operation without discontinuity in large flow detection and without needing to erase or reset the counters periodically is not provided.